import java.util.*;

public class Solution {
    public static void main(String[] args) {
        Solution test = new Solution();
//        Map<Character, Integer> a1 = new HashMap<>();
//        Map<Character, Integer> a2 = new HashMap<>();
//        a1.put('a', 2);
//        a1.put('b', 1);
//        a2.put('a', 2);
//        a2.put('b', 1);
//        System.out.println(a1.equals(a2));

        System.out.println(test.findAnagrams("aa", "bb"));
    }

    public int lengthOfLongestSubstring(String s) {
        /**
         * 无重复字符的最长子串
         * 本想优化，发现使用set后更加慢了，不过解决问题倒是可以
         * */
        // 1 预处理
        int n = s.length();
        char[] chars = s.toCharArray();

        // 2 双指针
        int left = 0;
        int right = 0;
        Set<Character> set = new HashSet<>();
        int maxSize = 0;
        while(right < n) {
            // -1 进窗口(由于set的缘故，需判断后再更新set)

            // -2 判断
            while(set.contains(chars[right])) {
                set.remove(chars[left]);
                left ++;
            }
            set.add(chars[right]);

            // -3 更新
            maxSize = Math.max(maxSize, right - left + 1);
            right ++;
        }

        // 3 返回值
        return maxSize;
    }

    public List<Integer> findAnagrams(String s, String pp) {
        /**
         * 找到字符串中所有字母的异位词
         * 思路：本题就相当于在字符串中找到所有元素相同的子串，因此我们使用固定窗口进行滑动遍历即可
         * 问题是现在应当使用什么样的方式进行存储？
         * set？ 不行，若是存在相同字符无法存储
         * ！map？ 可行，只不过不知道当key和value完全一致时，能不能比较相等 ==> 可以比较相等，只是时间复杂度较高，先做吧
         * char[]？可以比较，但是内部存储需要一致，所以会涉及排序，时间复杂度太高
         * 这一题看看老师的代码，我感觉优化要挺久，先做题吧，记着
         * */
        // 1 预处理
        int n = s.length();
        int m = pp.length();
        char[] chars = s.toCharArray();
        char[] p = pp.toCharArray();
        // -处理目标值
        Map<Character, Integer> target = new HashMap<>();
        for (char c : p) {
            if (target.containsKey(c)) {
                target.put(c, target.get(c) + 1);
            } else {
                target.put(c, 1);
            }
        }

        // 2 双指针
        int left = 0;
        int right = 0;
        Map<Character, Integer>  cur = new HashMap<>();
        List<Integer> retArray = new ArrayList<>();
        while(right < n) {
            // -1 进窗口
            if (cur.containsKey(chars[right])) {
                cur.put(chars[right], cur.get(chars[right]) + 1);
            } else {
                cur.put(chars[right], 1);
            }
            // -2 判断
            if(right - left + 1 == m) {
                if(cur.equals(target)) {
                    retArray.add(left);
                }
                // -3 出窗口
                cur.put(chars[left], cur.get(chars[left]) - 1);
                if(cur.get(chars[left]) == 0) {
                    cur.remove(chars[left]);
                }
                left ++;
            }
            right ++;
        }
        return retArray;
    }
}
